#ifndef _DINIC_H
#define _DINIC_H

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <map>

using std::queue; 
using std::vector;
using std::priority_queue;
using std::cout;
using std::endl;
using std::pair;

typedef vector<vector<int>> Mat;
typedef pair<int, int> P;




class Dinic {
public:
    struct edge {
        int nxt, to, w, cap, flow;
    };

    struct Brick{
        vector<int> pts;
        vector<P> corner{{}, {}, {}, {}};
        vector<P> mid_pts{{}, {}};
    };

    struct tree_edge {
        int from;
        int to;
        int cost;
        bool operator < (const tree_edge& e) const {
            return cost > e.cost;
        }
    };

    Dinic();
    ~Dinic();

    vector<Brick> bricks;
    void init(int n);

    void add_edge(int u, int v, int c);

    bool BFS();

    int DFS(int x, int a);

    int Maxflow(int s, int t);

    void get_cut(int u);

    P getEdgeCoor(int index, Mat& Map);

    Mat dinic_solver(Mat& Map, bool merge);

    void formBricksForMTSP(Mat& Map);

    bool checkMST(Mat& graph, Mat& Map);

    void mergeMST(Mat& graph, Mat& Map);

    // utility function
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y);

    bool isSameLine(int a, int b, int c) {
        return a + c == 2 * b;
    }

    int getEdgeVal(Mat& graph, int v1, int v2);
    int getVertexVal(Mat& graph, int v);

private:
//    int head[nmax], cur[nmax], d[nmax];
//    bool vis[nmax], iscut[nmax];
    int* head;
    int* cur;
    int* d;
    bool* vis;
    bool* iscut;
    int tot, n, m, s, t;
//    bool pts[nmax];
    bool *pts;
    vector<int> fa;
    edge *e;

};

#endif
